package com.gxc.string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 30. 串联所有单词的子串
 * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
 *
 *  s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
 *
 * 例如，如果 words = ["ab","cd","ef"]，
 * 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。
 * "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
 * 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
 */
public class FindSubstring {

    public static void main(String[] args) {
       /* String[] words = {"foo","bar"};
        println(handle("barfoothefoobarman", words));*/

        String[] words = {"word","good","best","good"};
        println(handle("wordgoodgoodgoodbestword", words));
    }

    /**
     *
     * @param s
     * @param words
     * @return
     */
    public static List<java.lang.Integer> handle(String s, String[] words) {
        int length = s.length();
        int m = words.length;
        int n = words[0].length();
        int wordLength = m*n;

        List<java.lang.Integer> res = new ArrayList<>();
        // 0....n,  n+1   后续的单词中再滑动窗口滑动的时候都是 0...n 单词组中都分割过一次
        for (int i = 0; i < n; i++) {
            if (i + wordLength > length) return res;
            Map<String, java.lang.Integer> diff = new HashMap<>();

            //初始化map，如果最后map为空，则说明滑动窗口内字符和目标字符匹配成功
            for (int j = 0; j < words.length; j++) {
                diff.put(words[j], diff.getOrDefault(words[j], 0) -1);
            }
            //从  i.。。。n+i分割s字符串，分成m个单词组，进行匹配
            for (int j = 0; j < m; j++) {
                String str = s.substring(i + j * n, i + n + j*n);
                diff.put(str, diff.getOrDefault(str, 0) +1);
                if (diff.get(str) == 0) {
                    diff.remove(str);
                }
            }
            if (diff.isEmpty()) {
                res.add(i);
            }
            //i。。n+i 不匹配，从开始滑动窗口，一次滑动n个单位，左边字符出map，右边字符进map
            for (int start = wordLength+i;start<=length-n;start = start+n) {
                //右边字符进map
                String str = s.substring(start, start+n);
                diff.put(str, diff.getOrDefault(str, 0) + 1);
                if (diff.get(str) == 0) {
                    diff.remove(str);
                }
                //左边字符出map
                str = s.substring(start-wordLength, start+n-wordLength);
                diff.put(str, diff.getOrDefault(str, 0) - 1);
                if (diff.get(str) == 0) {
                    diff.remove(str);
                }
                if (diff.isEmpty()) {
                    res.add(start - wordLength + n);
                }
            }
        }
        return res;
    }

    private static void println(List<java.lang.Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println("");
    }

    class Solution {

        /**
         * 滑动窗口
         * @param s
         * @param words
         * @return
         */
        public List<java.lang.Integer> findSubstring(String s, String[] words) {
            List<java.lang.Integer> res = new ArrayList<java.lang.Integer>();
            //数组大小
            int m = words.length;
            //单个单词的长度
            int n = words[0].length();
            //s的总长度
            int ls = s.length();
            //
            for (int i = 0; i < n; i++) {
                if (i + m * n > ls) {
                    break;
                }
                Map<String, java.lang.Integer> differ = new HashMap<String, java.lang.Integer>();
                //s 划分为单词组，每个单词的大小均为 n
                for (int j = 0; j < m; j++) {
                    String word = s.substring(i + j * n, i + (j + 1) * n);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);
                }
                //words 数组放入集合中，如果 differ 为空，则说明滑动窗口中的字符串和words 相等
                for (String word : words) {
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                }
                for (int start = i; start < ls - m * n + 1; start += n) {
                    if (start != i) {
                        String word = s.substring(start + (m - 1) * n, start + m * n);
                        differ.put(word, differ.getOrDefault(word, 0) + 1);
                        if (differ.get(word) == 0) {
                            differ.remove(word);
                        }
                        word = s.substring(start - n, start);
                        differ.put(word, differ.getOrDefault(word, 0) - 1);
                        if (differ.get(word) == 0) {
                            differ.remove(word);
                        }
                    }
                    //滑动窗口内字符串都匹配完毕，添加到结果集中
                    if (differ.isEmpty()) {
                        res.add(start);
                    }
                }
            }
            return res;
        }
    }

}
